'''
    SCC算法:
        SCC算法是求取图的强连通分量的一个算法，关于图的强连通分量的概念可以看文档。
        SCC算法也叫Kosaraju算法，其主要步骤如下：
            1. 调用 dfs 为图 G 计算每个顶点的完成时间。
            2. 计算 G^T 。
            3. 为图G^T 调用 dfs，但在 DFS 的主循环中，以完成时间的递减顺序探查每个顶点。
            4. 在步骤 3 中计算的森林中的每个树是强连通分量。输出森林中每个树中每个顶点的顶点标识组件。
'''

from graph import Graph

class DFSGraph(Graph):
    def __init__(self):
        super().__init__()
        self.time = 0   # 设置一个时间

    def dfs(self):
        for aVertex in self:
            aVertex.setColor('white')
            aVertex.setPred(-1)

        # 这里进行深度优先搜索时为什么要遍历：原因是可能有些顶点和其他顶点是不相连的，通过遍历可以确保每个顶点都能得到遍历。
        # 通过判断颜色是否为白色可以将之前判断过的顶点舍弃，实现节点只遍历一次
        for aVertex in self:
            if aVertex.getColor() == 'white':
                self.dfsVisit(aVertex)  # 运行一次深度优先搜索

    def dfsVisit(self,startVertex):
        startVertex.setColor('gray')    # 标记正在遍历
        self.time += 1
        startVertex.setDiscovery(self.time) # 发现时间

        for nextVertex in startVertex.getConnections():
            if nextVertex.getColor() == 'white':
                nextVertex.setPred(startVertex)
                self.dfsVisit(nextVertex)

        # 可以理解为该节点遍历完了
        startVertex.setColor('black')
        self.time += 1
        startVertex.setFinish(self.time)


def dfs(gt,dfsResult):
    res = []    # 存储所有黑色的顶点
    result = [] # 存储不同强连通区域的顶点
    for aVertex in gt:
        aVertex.setColor('white')
        aVertex.setPred(-1)
    for v in dfsResult:
        if gt.getVertex(v).getColor() == 'white':
            dfsvisit(gt,gt.getVertex(v))
            temp = []   # 存储最新变黑的顶点，也就是加到result中的东西
            for h in gt:
                if h.getColor() != 'white' and h.getId() not in res:
                    temp.append(h.getId())
            res = res + temp
            result.append(temp)
    return result

def dfsvisit(gt,startVertex):
    startVertex.setColor('gray')
    gt.time += 1
    startVertex.setDiscovery(gt.time)
    for nextVertex in startVertex.getConnections():
        if nextVertex.getColor() == 'white':
            nextVertex.setPred(startVertex)
            dfsvisit(gt,nextVertex)
    startVertex.setColor('black')
    gt.time += 1
    startVertex.setFinish(gt.time)


def main():
    # 主函数
    G = {
        'a': {'b', 'c'},
        'b': {'d', 'e', 'i'},
        'c': {'d'},
        'd': {'a', 'h'},
        'e': {'f'},
        'f': {'g'},
        'g': {'e', 'h'},
        'h': {'i'},
        'i': {'h'}
    }

    g = DFSGraph()  # 创建图
    gt = DFSGraph() # 创建转置图

    # 创建图
    for v in G:
        for w in G[v]:
            g.addEdge(v,w)

    # 打印图：
    print('图创建如下:')
    for v in g: # 这个返回的是键值：顶点
        for w in v.getConnections():
            print('\t(%s,%s,%s)' %(v.getId(),w.getId(),v.connectTo[w]))

    # 反转图，反转图有两种方式：1. 直接G字典里反转创建，2. 在原图中进行反转创建
    # 采用第二种方式
    gt = DFSGraph()
    for v in g: # 这个返回的是键值：顶点
        for w in v.getConnections():
            gt.addEdge(w.getId(),v.getId())

    # 原图尽心DFS并按照结束时间进行降序排列
    g.dfs() # 深度优先搜索
    res = []    # 拓扑排序结果
    for v in g: # 顶点
        temp = v.getFinish()
        res.append((v.getId(),temp))
    res.sort(reverse= True,key=lambda x:x[1])
    dfsResult = [y[0] for y in res]
    print('拓扑排序结果: ',dfsResult)

    # 转置图按照拓扑排序结果进行DFS
    result = dfs(gt,dfsResult)
    print('强连通区域：',result)

# 成功实现Kosaraju算法。
if __name__ == '__main__':
    main()